# 111. 二叉树的最小深度
# 给定一个二叉树，找出其最小深度。
# 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
# 说明：叶子节点是指没有子节点的节点。
#
# 示例 1：
# 输入：root = [3,9,20,null,null,15,7]
# 输出：2
#
# 示例 2：
# 输入：root = [2,null,3,null,4,null,5,null,6]
# 输出：5


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def minDepth(self, root):
        from collections import deque
        que = deque()
        count = 0
        if not root:
            return count
        que.append(root)
        while que:
            size = len(que)
            for i in range(size):
                cur = que.popleft()
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
                if not cur.left and not cur.right:
                    return count + 1
            count += 1


if __name__ == '__main__':
    # a31 = TreeNode(15)
    # a32 = TreeNode(7)
    # a21 = TreeNode(9)
    # a22 = TreeNode(20,a31,a32)
    # a11 = TreeNode(3,a21,5a22)
    # tmp = Solution()
    # res = tmp.minDepth(root=a11)
    # print(res)

    a5 = TreeNode(6)
    a4 = TreeNode(5,right=a5)
    a3 = TreeNode(4,right=a4)
    a2 = TreeNode(3,right=a3)
    a1 = TreeNode(2,right=a2)
    tmp = Solution()
    res = tmp.minDepth(a1)
    print(res)
